// 动态规划 - 核心 5 步：
// 1. 确定状态表示 - 根据 题目要求，经验(以 i,j 位置为结尾/开始......)，发现重复子问题 确定状态表示
// 2. 推导状态转移方程: dp[i] = ?
//    用 之前的状态 或者 之后的状态 推导当前的状态（根据最近一步划分问题）
// 3. 初始化：保证填表时不越界，结合多开数组的技巧
// 4. 确定填表顺序：填写当前状态值的时候，所需状态的值已经计算过了
// 5. 返回值：结合题目要求 + 状态表示

// 技巧：
// 01 背包问题：使用滚动数组进行优化，删除横坐标，从右往左填表
// 完全背包问题：使用滚动数组进行优化，删除横坐标，从左往右填表
// 似包非包问题：从重复子问题的角度入手分析 dp

// 例题 11:
// 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
//
//        题目数据保证答案符合 32 位整数范围。
//
//        示例 1：
//
//        输入：nums = [1,2,3], target = 4
//        输出：7
//        解释：
//        所有可能的组合为：
//        (1, 1, 1, 1)
//        (1, 1, 2)
//        (1, 2, 1)
//        (1, 3)
//        (2, 1, 1)
//        (2, 2)
//        (3, 1)
//        请注意，顺序不同的序列被视作不同的组合。
//        示例 2：
//
//        输入：nums = [9], target = 3
//        输出：0
//
//
//        提示：
//
//        1 <= nums.length <= 200
//        1 <= nums[i] <= 1000
//        nums 中的所有元素 互不相同
//        1 <= target <= 1000
//
//
//        进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

// 解题思路:
// 从示例上看，这是一个排列问题，无法用背包问题的思路解决
// 改用重复子问题的思路，类似 dfs:
// 选数字游戏，题目中需要凑成和 target，如果我们选了一个数字 num，需要凑成的和就变成 target - num
// 每次都需要选一个数字，直至凑成 target，因此这就是一个重复子问题
// dp[i] 表示凑成 i 的排列数
// 题目中不会出现重复数字，根据任意一个数字 nums[j] 分析：
// if(target > nums[j]) dp[i] += dp[target - nums[j]]

public class CombinationSum4 {
    public int combinationSum4(int[] nums, int target) {
        int n = nums.length;
        int[] dp = new int[target + 1];

        dp[0] = 1;

        for(int i = 1; i <= target; i++){
            for(int j = 0; j < n; j++){
                if(i - nums[j] >= 0){
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
}
